\documentclass[a4paper]{article}

\usepackage{alltt}
\usepackage{ascmac}
\usepackage[bookmarks=true,bookmarksnumbered=true,bookmarkstype=toc]{hyperref}

\newcounter{program}

\title{Cream version 1.2 Programmers Guide}
\date{Oct. 5, 2004}
\author{Naoyuki Tamura\\tamura@kobe-u.ac.jp\\\href{http://bach.istc.kobe-u.ac.jp/cream/}{http:{\slash}{\slash}bach.istc.kobe-u.ac.jp{\slash}cream{\slash}}}
\begin{document}

\pagestyle{empty}
\maketitle

\begin{abstract}
This document describes how to write Java programs in Cream (Constraint Resolution Enhancement And Modules) class library. In other words, \textbf{how to make your Java creamy}.\end{abstract}

\pagestyle{empty}


\tableofcontents

\clearpage

\pagenumbering{arabic}
\pagestyle{plain}


\section{Features}
\suppressfloats[t]


Cream is a class library helping Java programmers to develop intelligent programs
requiring constraint satisfaction or optimization on finite domains.
The followings are features of Cream.

\begin{itemize}
\item 100{\%} Pure Java: Whole programs are written in Java.
\item Open source: Cream is distributed as a free software with source code. Please refer to \hyperlink{hyperrefdoc1:128}{License section} for more details about licensing issue.
\item Natural description of constraints: Various constraints can be naturally described within Java syntax.
\item Easy enhancements: Programmers can easily enhance{\slash}extend constraint descriptions and satisfaction algorithms.
\item Various optimization algorithms: Various optimization algorithms are available, such as Simulated Annealing, Taboo Search, etc.
\end{itemize}





\section{Installation}
\suppressfloats[t]


There is nothing special for installation.
Please \texttt{unzip} the \texttt{zip} file you can obtained from the web page,
then you are ready to 
run example programs in \texttt{examples} directory as follows.

\begin{itemize}
\item on Unix-like systems:
\bigskip
\begin{screen}
\begin{alltt}
  java -classpath .:../cream.jar FourColor
\end{alltt}
\end{screen}
\bigskip
\item on Windows systems:
\bigskip
\begin{screen}
\begin{alltt}
  java -classpath .;..\(\backslash\)cream.jar FourColor
\end{alltt}
\end{screen}
\bigskip
\end{itemize}


Please note that you need
\href{http://java.sun.com/j2se/}{Java 2, Standard Edition} to use Cream.



\section{Programming}
\suppressfloats[t]


\subsection{First Step}


This section describes how to use Cream step-by-step.

Consider an old Japanese elementary school problem:
\begin{quotation}
There are some cranes and tortoises. They are 7 in total, and their legs are 20 in total. How many cranes and tortoises are there?
\end{quotation}

To solve this problem in Cream, firstly
you need to create a constraint network (an instance of \texttt{Network} class)
consisting of variables and constraints over those variables.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    Network net = new Network();
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip


Secondly, please declare and create variables for numbers of 
cranes (that is, \texttt{x}) and tortoises (that is, \texttt{y}).

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    IntVariable x = new IntVariable(net);
    IntVariable y = new IntVariable(net);
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip


These variables are added to the constraint network by the constructor.

Thirdly, please describe constraint conditions over those variables,
that is \texttt{x $>$= 0}, \texttt{y $>$= 0},
\texttt{x + y == 7}, and \texttt{2x + 4y == 20}.
First two conditions can be written in Cream as follows.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    x.ge(0);
    y.ge(0);
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip


These constraints are also added to the same constraint network
which the variables belong.

It is possible to write them (but lengthy) as follows.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    new IntComparison(net, IntComparison.GE, x, 0);
    new IntComparison(net, IntComparison.GE, y, 0);
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip



The latter two conditions \texttt{x + y == 7} and \texttt{2x + 4y == 20}
can be written simply as follows.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    x.add(y).equals(7);
    x.multiply(2).add(y.multiply(4)).equals(20);
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip



It is possible to rewrite them as follows.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    // 7 == x + y
    new IntArith(net, IntArith.ADD, 7, x, y);
    // t1 == x * 2
    IntVariable t1 = new IntVariable(net);
    new IntArith(net, IntArith.MULTIPLY, t1, x, 2);
    // t2 == y * 4
    IntVariable t2 = new IntVariable(net);
    new IntArith(net, IntArith.MULTIPLY, t2, y, 4);
    // 20 == t1 + t2
    new IntArith(net, IntArith.ADD, 20, t1, t2);
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip



Now, pass the constraint network to
\texttt{DefaultSolver} to solve the problem by constraint propagation and backtracking.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    Solver solver = new DefaultSolver(net);
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip



You can get a solution from the solver as follows.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    Solution solution = solver.findFirst();
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip


This code only finds the first solution, but it is sufficient in this case.

To get values of the variables in the solution, \texttt{getIntValue} methods can be used.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    int xv = solution.getIntValue(x);
    int yv = solution.getIntValue(y);
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip



The following is the whole program.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
/*
 * @(#)FirstStep.java
 */
import jp.ac.kobe_u.cs.cream.*;

public class FirstStep {\{}
    public static void main(String args[]) {\{}
        // Create a constraint network
        Network net = new Network();
        // Declare variables
        IntVariable x = new IntVariable(net);
        IntVariable y = new IntVariable(net);
        // x >= 0
        x.ge(0);
        // y >= 0
        y.ge(0);
        // x + y == 7
        x.add(y).equals(7);
        // 2x + 4y == 20
        x.multiply(2).add(y.multiply(4)).equals(20);
        // Solve the problem
        Solver solver = new DefaultSolver(net);
        Solution solution = solver.findFirst();
        int xv = solution.getIntValue(x);
        int yv = solution.getIntValue(y);
        System.out.println("x = " + xv + ", y = " + yv);
    {\}}
{\}}
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip



The same program is in \texttt{examples} directory.
You can compile and execute it as follows.

\begin{itemize}
\item on Unix-like systems:
\bigskip
\begin{screen}
\begin{alltt}
  javac -classpath .:../cream.jar FirstStep.java
  java -classpath .:../cream.jar FirstStep
\end{alltt}
\end{screen}
\bigskip
\item on Windows systems:
\bigskip
\begin{screen}
\begin{alltt}
  javac -classpath .;..\(\backslash\)cream.jar FirstStep.java
  java -classpath .;..\(\backslash\)cream.jar FirstStep
\end{alltt}
\end{screen}
\bigskip
\end{itemize}





\subsection{Using Coroutining Facility}


If you want to find all solutions, you can use 
coroutining facility or \texttt{SolutionHandler} interface described in the next subsection.

The previous example program can be rewritten as follows.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    Solver solver = new DefaultSolver(net);
    for (solver.start(); solver.waitNext(); solver.resume()) {\{}
        Solution solution = solver.getSolution();
        int xv = solution.getIntValue(x);
        int yv = solution.getIntValue(y);
        System.out.println("x = " + xv + ", y = " + yv);
    {\}}
    solver.stop();
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip


The \texttt{start()} method starts the solver in a new thread,
and immediately returns to the caller.
The \texttt{waitNext()} method is used to wait the next solution.
It returns \texttt{true} if the next solution is found, and returns
\texttt{false} if there are no more solutions.
The \texttt{getSolution()} method returns the solution.
The solver is suspended when the solution is found,
and it resumes the execution when the \texttt{resume()} method is called.
The \texttt{stop()} method should be called so that the solver thread is disposed cleanly.

The invocation of the \texttt{stop()} method during the search results in the abortion of
the solver execution.



\subsection{Using SolutionHandler}


\texttt{SolutionHandler} can be used to find all solutions.
The previous example program can be rewritten as follows.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    Solver solver = new DefaultSolver(net);
    solver.findAll(new FirstStepHandler(x, y));
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip


The \texttt{findAll(SolutionHandler handler)} invokes
\texttt{solved} method of the handler for each solution and at the end of the solver execution.

The following is an example implementation of the \texttt{SolutionHandler}.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
class FirstStepHandler implements SolutionHandler {\{}
    IntVariable x;
    IntVariable y;

    public FirstStepHandler(IntVariable x, IntVariable y) {\{}
        this.x = x;
        this.y = y;
    {\}}

    public synchronized void solved(Solver solver, Solution solution) {\{}
        if (solution != null) {\{}
            int xv = solution.getIntValue(x);
            int yv = solution.getIntValue(y);
            System.out.println("x = " + xv + ", y = " + yv);
        {\}}
    {\}}
{\}}
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip



Another way is the use of \texttt{start(SolutionHandler handler)} method.
It starts the solver in a new thread, and immediately returns to the caller.
You can wait the end of the solver execution by \texttt{join()} method.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    Solver solver = new DefaultSolver(net);
    solver.start(new FirstStepHandler(x, y));
    /* other jobs can be performed in parallel */
    solver.join();
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip





\subsection{Searching with Timeout}


Above mentioned methods (\texttt{findFirst}, \texttt{findAll}, and \texttt{start}) have
optional argument for specifying timeout in milliseconds.

\begin{itemize}
\item \texttt{findFirst(long timeout)}
\item \texttt{findAll(SolutionHandler handler, long timeout)}
\item \texttt{start(long timeout)}
\item \texttt{start(SolutionHandler handler, long timeout)}
\end{itemize}



The solver stops the execution when the elapsed time exceeds the given timeout value.

It is also possible to specify the timeout value for the \texttt{waitNext} method.





\subsection{Finding Optimal Solution}


The following is an outline of a program to find the optimal solution
by complete search.

\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    // set the objective variable
    net.setObjective(v);

    // set the solver to find the minimal value
    Solver solve = new DefaultSolver(net, Solver.MINIMIZE);
    for (solver.start(); solver.waitNext(); solver.resume()) {\{}
        // find the next better solution
        Solution solution = solver.getSolution();
        .....
    {\}}
    solver.stop();

    // get the best solution
    Solution solution = solver.getBestSolution();
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip


The method \texttt{getBestSolution} always return 
the best solution up to now.



\subsection{Using Local Search}


Currently, Cream can solve a problem by local search when the problem 
involves \texttt{Serialized} constraints.

\begin{itemize}
\item \texttt{Serialized(Variable{[}{]} \textit{s}, int{[}{]} \textit{d})}

All intervals
  \texttt{{[}\textit{si}, \textit{si}+\textit{di}-1{]}}
  are not overlapped each other
\item Useful for scheduling problems
\end{itemize}


The following local search algorithms are available in Cream.

\begin{itemize}
\item \texttt{LocalSearch()}: Random Walk
\item \texttt{SASearch()}: Simulated Annealing
\item \texttt{TabooSearch()}: Taboo Search
\item \texttt{IBBSearch()}: Iterative Branch and Bound
\end{itemize}



\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    net.setObjective(v);

    long timeout = 60000;

    Solver solve = new SASearch(net, Solver.MINIMIZE);
    for (solver.start(timeout); solver.waitNext(); solver.resume()) {\{}
        // find the next neighbor solution
        Solution solution = solver.getSolution();
        .....
    {\}}
    solver.stop();

    // get the best solution
    Solution solution = solver.getBestSolution();
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip





\subsection{Using Multiple Local Search Solvers}



\begin{itemize}
\item Cream also allows to use multiple local search solvers working in parallel (multi thread).
\item Each solver randomly post its current best solution
\item Other solvers randomly adopt the posted solution to generate the next neighbor
\end{itemize}



\bigskip

{\small {\hrule\endgraf\vspace*{1pt}\hrule}
\nobreak
\begin{alltt}
    Solver solver1 = new SASearch((Network).net.clone(), Solver.MINIMIZE);
    Solver solver2 = new TabooSearch((Network).net.clone(), Solver.MINIMIZE);
    Solver[] solvers = {\{} solver1, solver2 {\}};
    Solver solver = new ParallelSolver(solvers);

    for (solver.start(timeout); solver.waitNext(); solver.resume()) {\{}
        Solution solution = solver.getSolution();
        .....
    {\}}
    solver.stop();

    Solution solution = solver.getBestSolution();
\end{alltt}
\nobreak
{\hrule\endgraf\vspace*{1pt}\hrule}
}
\bigskip








\section{API}
\suppressfloats[t]


See \href{../../api/index.html}{Cream API Specification}.



\section{License}
\hypertarget{hyperrefdoc1:128}{}\label{doc1:128}
\suppressfloats[t]



\begin{description}
\item [Cream (Class Library for Constraint Programming in Java)] \item [Copyright (C) 2003, 2004 by Naoyuki Tamura (tamura@kobe-u.ac.jp)] \end{description}


Cream is free software; you can redistribute it and{\slash}or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA



\section{Acknowledgement}
\suppressfloats[t]


Cream was developed as a part of
\href{http://kaminari.scitec.kobe-u.ac.jp/hecs/}{HECS
(HEterogeneous Constraint Solver) system} which was supported in part
by 
\href{http://www.meti.go.jp/}{METI} and
\href{http://www.ipa.go.jp/}{IPA (The Information-technology Promotion Agency)}
under grant of
\href{http://www.ipa.go.jp/NBP/14nendo/14mito/}{2002 Exploratory Software Project} and
\href{http://www.ipa.go.jp/NBP/15nendo/15mito/}{2003 Exploratory Software Project}.
Some improvement ideas of Cream are obtained through the discussion with
Mr. Kino, a project manager of IPA Exploratory Software Project
and also a developer of \href{http://www.kprolog.com}{K-Prolog} and 
\href{http://www.isac.co.jp/ICS/ics_injava.html}{ICS in Java}.



\end{document}
